"""
2. 钢条切割
    某公司， 出售价格与钢条长度之间的关系如下
    tn
        长度 1  2  3  4  5  6  7  8  9  10
        价格 1  5  8  9  10 17 17 20 24 30
    
    问题： 现有长度为n的钢条和上面的价格表，求切割钢条方案，使得总收益最大。
    
    解析：
        递归（自顶向下）：
            求出来指定范围内每个长度的最优解。直接用最优解进行更大长度的计算。
            
        rn
            长度 0  1  2  3  4  5  6  7  8  9  10
            价格 0  1  5  8  10 13 17 18 22 25 30
            
            可以求出来 rn(在指定范围1 - 10的最优解), 的递推式：
            
            rn = max(pn, (rn-1)+r1, ..., (rn-2)+rn)
            
            pn 表示不切割
            
            总结（最优子结构）：
                可以将求解规模为n的原问题，划分为规模更小的子问题：完成一次切割后，可以将产生的两段钢条堪称两个独立的钢条切割问题。
                
                组合两个子问题的最优解，并在所有可能的两端切割方案中选取组合收益最大的，构成原问题的最优解。
                
                钢条切割满足最有子结构：问题的最优解由相关子问题的最优解组合而成，这些子问题可以独立求解。
            
            
        优化：
            从钢条的左边切割下长度为i的一段，只对右边剩下的一段继续进行切割，左边不在切割
            
            递推式简化为 rn = max(pi + rn-i)  其中 1 <=i <= n
            
            不做切割的方案就可以描述为：左边一段长度为n， 收益为pn, 剩余一段长度为0， 收益为r0 = 0
            
            原因： 例如：
                9 可以切为 2 3 2 2 
                可以看成 5 和 4
                也可以看成 2 和 7 将7切为 3  2  2
                
        
        动态规划解法(自底向上)：
            因为递归引起的子结构重复计算，那么我们就使用动态规划，将子结构的值存起来


扩展：展示切割方案
    1. 只记录左边的，因为左边是不切割的
    2. 对于右边这块， 不断的向下找左边的， 直到找到 右边为0的

"""


"""
    总结： 钢条切割问题我们去不断的分割求出来每一段的最优解， 加起来是不是就是要求的最优解
"""
price = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
zz =    [0, 1, 5]
# 解法1
def getMax(price, n):
    """
        将大的不断的拆成小的， 然后去找每个小的最大值， 所有小的最大值加起来就是当前的最大值
    """
    if n == 0:
        return 0
    res = price[n]
    for i in range(1, n):
        res = max(res, getMax(price, i)+getMax(price, n-i))
    return res

result = getMax(price, 5)
print(result)

# 解法二， 只对一边做切割
"""
2 4 3
2 7
7 分割 4 3

递归出口就是 左侧变成0的时候
"""

def getMax2(price, n):
    if n == 0:
        return 0
    res = 0
    for i in range(1, n+1):
        res = max(res, price[i]+getMax2(price, n-i))
    return res

# res = max(res, price[1] + getMax2(price, 4))
# res = max(res, price[2] + getMax2(price, 3))
# res = max(res, price[3] + getMax2(price, 2))
# res = max(res, price[4] + getMax2(price, 1))
# res = max(res, price[5] + getMax2(price, 0))

result2 = getMax2(price, 5)
print(result2)

"""
    动态规划思想
"""

# 解法三
def getMax3(price, n):
    # 存放每一段的最大值
    data = [0]
    
    for i in range(1, n+1):
        res = 0
        for j in range(1, i+1):
            # 这个时候， 左边不切割， 右边切割，只对右边求最大
            res = max(res, price[j] + data[i-j])
        data.append(res)
    return data[n]
"""
    先求 1的最大值，  把最大值放进去
    再求 2 的最大值， 把最大值放进去
    去最大值的时候直接从 data 中取就行了
    第二个循环实际上就是， 循环找此阶段的最大值
    
"""
result3 = getMax3(price, 5)
print(result3)

# 扩展输出切割方法：
"""
    思路， 对每一小段最大值的最左侧进行记录， 然后根据记录循环找完右侧，就是切割结果
"""

def getMax4(price, n):
    data = [0]
    s = [0]
    for i in range(1, n+1):
        res = 0
        res_l = 0
        for j in range(1, i + 1):
            if price[j] + data[i - j] > res:
                res =  price[j] + data[i - j]
                res_l = j
        data.append(res)
        s.append(res_l)
    return data[n], s

def get_len(s, n):
    """
        先把最左侧的放进去
        找最右侧， 再把最右侧的最左侧放进去
        直到找完为止，找完就是指，长度减完了
    """
    result = []
    while n > 0:
        # 先把最左侧的放进去
        result.append(s[n])
        # 找右侧
        n -= s[n]
    return result

res, res_l = getMax4(price, 10)
result = get_len(res_l, 10)
print(res, result)
    
    